package com.wjy.Data_Structure.sort.sort2;

import java.util.Arrays;

import com.wjy.Data_Structure.sort.DataWrap;

public class QuickSort {
	private static void swap(DataWrap[] data, int i, int j) {
		DataWrap tmp;
		tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}

	//对data数组中从start到end索引范围的子序列进行处理
	private static void subSort(DataWrap[] data, int start, int end) {
		//需要排序
		if (start < end) {
			//以第一个元素作为分界值
			DataWrap base = data[start];
			//i从左开始搜索
			int i = start;
			//j从右开始搜索
			int j = end + 1;
			while (true) {
				while (i < end && data[++i].compareTo(base) <= 0)
					;
				while (j > start && data[--j].compareTo(base) >= 0)
					;
				if (i < j) {
					swap(data, i, j);
				} else {
					break;
				}
			}
			swap(data, start, j);
			//递归左边子序列
			subSort(data, start, j - 1);
			//递归右边子序列
			subSort(data, j + 1, end);
		}

	}

	//快速排序
	public static void quickSort(DataWrap[] data) {
		subSort(data, 0, data.length - 1);
	}

	public static void main(String[] arys) {
		DataWrap[] data = { new DataWrap(21, ""), new DataWrap(30, ""), new DataWrap(49, ""), new DataWrap(30, ""),
				new DataWrap(16, ""), new DataWrap(9, ""), };
		System.out.println("排序之前：\n" + Arrays.toString(data));
		quickSort(data);
		System.out.println("排序之后：\n" + Arrays.toString(data));
	}
}
